import java.util.HashMap;

public class TwoSum {
    public static void main(String[] args) {
        int[] ints = twoSum(new int[]{2, 7, 11, 15}, 9);
        // 显示结果
        for (int i : ints) {
            System.out.print(i + " ");
        }
    }

    /**
     * 在给定数组中寻找两个数，使其和等于目标值，并返回它们的索引。
     * 使用哈希表存储遍历过的数值及其索引，实现时间复杂度 O(n) 的解法。
     * @param nums   整数数组，包含待搜索的数值
     * @param target 目标两数之和
     * @return 包含两个有效索引的数组（按升序排列），若不存在则返回空数组
     */
    public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> result = new HashMap<>();

        // 遍历数组，每次迭代检查当前元素的补数（target - nums[i]）是否存在于哈希表中
        for (int i = 0; i < nums.length - 1; i++) {
            int require = target - nums[i];

            // 发现有效补数时，立即返回两个索引（哈希表存储的旧索引在前，当前索引在后）
            if (result.containsKey(require)) {
                return new int[]{result.get(require), i};
            }

            // 将当前数值及其索引存入哈希表，供后续元素查询
            result.put(nums[i], i);
        }

        // 未找到有效解时返回空数组（根据LeetCode题目描述，实际用例保证存在解）
        return new int[]{};
    }


}
